package com.cat.dataStructure03;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/separate-squares-i/
 * @create 2025/11/10 20:33
 * @since JDK17
 */

class Solution41 {
    boolean check(int[][] squares, double y, long total) {
        double area = 0;
        for (var sq : squares) {
            double yy = sq[1];
            if (yy < y) {
                double l = sq[2];
                area += l * Math.min(y - yy, l);
            }
        }
        return area >= total / 2.0;
    }
    public double separateSquares(int[][] squares) {
        long total = 0;
        int maxy = 0;
        for (var sq : squares) {
            int l = sq[2];
            total += (long) l * l;
            maxy = Math.max(maxy, sq[1] + l);
        }
        double l = 0, r = maxy;
        for (int i = 0; i < 50; i++) {
            double mid = (l + r) / 2;
            if (check(squares, mid, total)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return (l + r) / 2;
    }
}